
package Planejamento.Caminho;

import Mapeamento.QuadTree.No;
import java.util.ArrayList;

/**
 *
 * @author jhielson
 */

public class Dijkstra {

    Grafo mapa;
    boolean fim;
    No temp;
    public ArrayList<No> caminho = new ArrayList<No>();
    public ArrayList<No> vizinhosAbertos = new ArrayList<No>();
    public ArrayList<No> perdidos = new ArrayList<No>();
    ArrayList<No> vertices = new ArrayList<No>();

    public Dijkstra(Grafo mapa)
    {
        this.mapa = mapa;
        mapa.inicio.estimativa = 0;
    }

    ////////////////////////////////////////////////////////////////////////////

    public void identificar()
    {
        No aux = mapa.fim;
        ArrayList<No> tem = new ArrayList<No>();

        caminho.add(aux);
        while(aux != mapa.inicio)
        {
            aux = aux.precedente;
            caminho.add(aux);
        }

        for(int i = caminho.size()-1; i >= 0; i--)
        {
            tem.add(caminho.get(i));
        }
        caminho = tem;
    }

    ////////////////////////////////////////////////////////////////////////////

    public void algoritmo()
    {
        vertices = (ArrayList<No>) mapa.listaNo.clone();
        No atual;

        while(!vertices.isEmpty())
        {
            //bubbleSort(vertices);
            inPlaceQuickSort(vertices, 0, vertices.size()-1);
            atual = vertices.remove(0);
            if(!atual.vizinhoss.isEmpty())
            {
                for(Aresta a: atual.vizinhoss)
                {
                    relaxamentoAresta(a.destino, atual, a.tamanho);
                }
            }   
        }
        identificar();
    }
    
    ////////////////////////////////////////////////////////////////////////////

    public void relaxamentoAresta(No vizinho, No atual, double peso)
    {
            if(atual.estimativa + peso < vizinho.estimativa )
            {
                vizinho.estimativa = atual.estimativa + peso;
                vizinho.precedente = atual;
            }
    }

    ////////////////////////////////////////////////////////////////////////////

      public void bubbleSort(ArrayList<No> q)
      {
       No t; // Variavel auxiliar
       for(int i = 0; i < q.size(); i++)
       {
         for(int j = 1; j <q.size()-i; j++)
         {
            if( q.get(j-1).estimativa > q.get(j).estimativa )
            {
                t = q.get(j-1);
                q.set(j-1, q.get(j));
                q.set(j, t);
            }
         }
       }          
      }

    ////////////////////////////////////////////////////////////////////////////

    public void inPlaceQuickSort(ArrayList<No> q, int a, int b)
    {
        No p, t;
        int l,r;

        if(a>=b)
           return;

        p = q.get(b);
        l = a;
        r = b-1;

        while(l<=r)
        {
            while(l<=r && q.get(l).estimativa<=p.estimativa)
            {
                l++;
            }
            while(r>=l && q.get(r).estimativa>=p.estimativa)
            {
                r--;
            }
            if(l<r)
            {
                t = q.get(l);
                q.set(l, q.get(r));
                q.set(r, t);
            }
        }

        t = q.get(l);
        q.set(l, q.get(b));
        q.set(b, t);

        inPlaceQuickSort(q,a,l-1);
        inPlaceQuickSort(q,l+1,b);
    }
}
